package com.explorati.dongtaiguihua.LeetCode343;

import java.util.Arrays;

/**
 * 343. Integer Break
 * 
 * Given a positive integer n, break it into the sum of at least two positive
 * integers and maximize the product of those integers. Return the maximum
 * product you can get.
 * 
 * Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
 * 
 * 暴力解法：回溯遍历将一个数做分割的所有可能性 O(2^n)
 * 
 * 方法一：记忆化搜索
 * 
 * @author explorati
 *
 */
public class Solution {

	int[] memo;

	// 将n进行分割(至少分割成两部分)，可以获得的最大乘积
	public int breakInteger(int n) {
		if (n == 1) {
			return 1;
		}

		if (memo[n] != -1) {
			return memo[n];
		}

		int res = -1;
		for (int i = 1; i <= n - 1; i++) {
			// i + (n - i)
			res = Max(res, i * (n - i), i * breakInteger(n - i));
		}
		memo[n] = res;
		return res;
	}

	public static int Max(int a, int b, int c) {
		return Math.max(a, Math.max(b, c));
		// if (Math.max(a, b) > c) {
		// return c;
		// } else {
		// return Math.max(a, b);
		// }
	}

	public int integerBreak(int n) {
		memo = new int[n + 1];
		Arrays.fill(memo, -1);
		return breakInteger(n);
	}
}
